/*归并排序
 *
 */
#include "mergesort.h"
#include <qdebug.h>

MergeSort::MergeSort()
{

}

void mergesort(int *array, int length)
{
    if(array==NULL || length <1)
        return;
    if(length>1){
        int list1_size=length/2;
        int *list1=array;

        int list2_size=length-list1_size;
        int *list2=array+list1_size;

        mergesort(list1,list1_size);
        mergesort(list2,list2_size);

        merging(list1,list1_size,list2,list2_size);
    }
}

void merging(int *list1, int list1_size, int *list2, int list2_size)
{
    if(list1==NULL || list2==NULL || list1_size<1 ||list2_size<1)
        return;

    int i,j,index;
    i=j=index=0;
    int tmp[MAXSIZE]={0};

    while(i<list1_size && j<list2_size){
        if(list1[i]<list2[j])
            tmp[index++]=list1[i++];
        else
            tmp[index++]=list2[j++];
    }
    while(i<list1_size)
        tmp[index++]=list1[i++];
    while(j<list2_size)
        tmp[index++]=list2[j++];

    for(i=0;i<index;++i)
        list1[i]=tmp[i];

//    qDebug()<<"index:"<<index;
}
